МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ „ЛЬВІВСЬКА ПОЛІТЕХНІКА”
Лабораторна робота №1
Проектування засобів захисту інформації в комп’ютерних мережах
«Обчислення хеш-функції за алгоритмом SHA-1»
Львів – 2015
Мета роботи: реалізувати програму обчислення значення сигнатури вхідного повідомлення за алгоритмом SHA-1.
Теоретичні відомості
Хеш-функція SHA-1 - безпечний хеш-алгоритм (Secure Hash Algorithm) був розроблений національним інститутом стандартів і технології (NIST) і опублікований в якості федерального інформаційного стандарту (FIPS PUB 180) в 1993 році. SHA-1, як і MD5, заснований на алгоритмі MD4.
Логіка виконання SHA-1
Алгоритм отримує на вході повідомлення максимальної довжини 2 64 біт і створює в якості виходу дайджест повідомлення довжиною 160 біт.
Алгоритм складається з наступних кроків:
Крок 1: додавання бракуючих бітів
Повідомлення додається таким чином, щоб його довжина була кратна 448 по модулю 512 (довжина 448 mod 512). Додавання здійснюється завжди, навіть якщо повідомлення вже має потрібну довжину. Таким чином, число додаваних бітів знаходиться в діапазоні від 1 до 512. Додавання складається з одиниці, за якою слід необхідну кількість нулів.
Крок 2: додавання довжини
До повідомлення додається блок з 64 бітів. Цей блок трактується як беззнаковое 64-бітне ціле і містить довжину вихідного повідомлення до додавання. Результатом перших двох кроків є повідомлення, довжина якого кратна 512 бітам. Розширене повідомлення може бути представлене як послідовність 512-бітних блоків Y0, Y1,. . . , YL-1, так що загальна довжина розширеного повідомлення є L * 512 біт. Таким чином, результат кратний шістнадцяти 32-бітними словам.
Крок 3: ініціалізація SHA-1 буфера
Використовується 160-бітний буфер для зберігання проміжних та остаточних результатів хеш-функції. Буфер може бути представлений як п'ять 32-бітних регістрів A, B, C, D і E. Ці регістри ініціалізується наступними шістнадцятковому числами:
A = 67452301
B = EFCDAB89
C = 98BADCFE
D = 10325476
E = C3D2E1F0
Крок 4: обробка повідомлення в 512-бітних блоках
Основою алгоритму є модуль, що складається з 80 циклічних обробок, позначений як HSHA. Всі 80 циклічних обробок мають однакову структуру.
Кожен цикл отримує на вході поточний 512-бітний обробляємий блок Yq і 160-bit значення буфера ABCDE, і змінює вміст цього буфера.
У кожному циклі використовується додаткова константа Кt, яка приймає тільки чотири різних значення:
0 ≤ t ≤ 19 K t = 5A827999 (ціла частина числа [230 × 21/2])
20 ≤ t ≤ 39 K t = 6ED9EBA1 (ціла частина числа [230 × 31/2])
40 ≤ t ≤ 59 K t = 8F1BBCDC (ціла частина числа [230 × 51/2])
60 ≤ t ≤ 79 K t = CA62C1D6 (ціла частина числа [230 × 101/2])
Для отримання SHA q +1 вихід 80-го циклу складається зі значенням SHAq. Додавання за модулем 232 виконується незалежно для кожного з п'яти слів в буфері з кожним з відповідних слів у SHAq.
Крок 5: вихід
Після обробки всіх 512-бітних блоків виходом L-ої стадії є 160-бітний дайджест повідомлення.
Розглянемо більш детально логіку в кожному з 80 циклів обробки одного 512-бітного блоку. Кожен цикл можна представити у вигляді:
A, B, C, D, E (CLS5 (A) + f t (B, C, D) + E + W t + K t), A, CLS30 (B), C, D
де
A, B, C, D, E - п'ять слів з буфера.
t - номер циклу, 0 t 79.
f t - елементарна логічна функція.
CLS s - циклічний лівий зсув 32-бітного аргументу на s бітів.
W t - 32-бітне слово, отримане з поточного вхідного 512-бітного блоку.
K t - додаткова константа.
+ - Додавання за модулем 2 32.
Кожна елементарна функція одержує на вході три 32-бітних слова і створює на виході одне 32-бітне слово. Елементарна функція виконує набір побітних логічних операцій, тобто n-ий біт виходу є функцією від n-их бітів трьох входів. Функції такі:
Номер циклу ft (B, C, D)
Насправді використовуються тільки три різні функції. Для 0 ≤ t ≤ 19 функція є умовною: if B then C else D. Дл...